package demo.practice.uf;

public class UFNumsUnion {


    int[] parent;
    int[] nums;//节点数

    public UFNumsUnion(int size) {
        parent = new int[size];
        nums = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            nums[i] = 1;
        }
    }

    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }

    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            //a节点多，就将 b节点往a节点上合并，这样的话可以减少树的高度
            if (nums[ap] > nums[bp]) {
                parent[bp] = ap;
                nums[ap] += nums[bp];    //根节点的节点数  增加了  被合并节点的节点数
            } else {
                parent[ap] = bp;
                nums[bp] += nums[ap];
            }
        }
    }


    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }

}
